#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Solution {
    public:
        void rotate(vector<vector<int> > &matrix) {
            int size = matrix.size();
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size-i; j++) {
                    int tmp = matrix[i][j];
                    matrix[i][j] = matrix[size-1-j][size-1-i];
                    matrix[size-1-j][size-1-i] = tmp;
                }
            }
            int start = 0, end = size-1;
            while (start < end) {
                for (int i = 0; i < size; i++) {
                    int tmp = matrix[start][i];
                    matrix[start][i] = matrix[end][i];
                    matrix[end][i] = tmp;
                }
                start++;
                end--;
            }
        }
};

//add better code
    void rotate(vector<vector<int> > &matrix) {
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = i; j < matrix[0].size(); j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp; 
            }    
        }    
        for (int i = 0; i < matrix.size(); i++) {
            int k = 0, l = matrix[0].size()-1;
            while(k < l) { 
                int tmp = matrix[i][k];
                matrix[i][k] = matrix[i][l];
                matrix[i][l] = tmp; 
                k++;
                l--;
            }    
        }    
    }

//test on 1337 onlie judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;
    vector<vector<int> > matrix;

    cout << "-----------------Test 1--------------------" << endl;
    vector<int> row1, row2, row3;
    row1.push_back(1); 
    row1.push_back(2); 
    row1.push_back(3); 
    row2.push_back(4); 
    row2.push_back(5); 
    row2.push_back(6); 
    row3.push_back(7); 
    row3.push_back(8); 
    row3.push_back(9); 
    matrix.push_back(row1);
    matrix.push_back(row2);
    matrix.push_back(row3);
    mySolution.rotate(matrix);
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++)
            cout << matrix[i][j] << " ";
        cout << endl;
    }

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
